from collections import defaultdict, deque
from typing import List


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = wordList.copy()
        s, t = None, None
        for i, w in enumerate(wordList):
            if w == beginWord:
                s = i
            if w == endWord:
                t = i
        if t is None:
            return 0
        if s is None:
            wordList.append(beginWord)
            s = len(wordList) - 1

        book = defaultdict(list)
        for u, w in enumerate(wordList):
            for i in range(len(w)):
                book[(w[:i] + w[i+1:], i)].append(u)
        book = {k: v for k, v in book.items() if len(v) > 1}

        def bfs():
            n = len(wordList)
            inf = 2 ** 30
            d = [inf] * n
            d[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                if u == t:
                    return d[t]
                wu = wordList[u]
                for i in range(len(wu)):
                    k = (wu[:i] + wu[i + 1:], i)
                    if k in book:
                        for v in book[k]:
                            if wordList[v][i] != wu[i] and d[v] == inf:
                                d[v] = d[u] + 1
                                q.append(v)
            return -1

        distance = bfs()
        return distance + 1

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print(Solution().ladderLength(beginWord, endWord, wordList))